const Graph = require("../template")

function testGraphPathfinding() {
  console.log(
    "1. 最短路径测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['B', 'C'], ['C', 'D'], ['A', 'D']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const path = graph.shortestPath('A', 'D')
      
      return path.length === 2 && // A -> D (直接路径)
             path[0] === 'A' &&
             path[1] === 'D'
    })()
  )

  console.log(
    "2. 多步路径测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['B', 'C'], ['C', 'D']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const path = graph.shortestPath('A', 'D')
      
      return path.length === 4 && // A -> B -> C -> D
             path[0] === 'A' &&
             path[1] === 'B' &&
             path[2] === 'C' &&
             path[3] === 'D'
    })()
  )

  console.log(
    "3. 无路径测试:",
    (() => {
      const graph = new Graph()
      
      // 构建不连通的图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['C', 'D']] // A-B 和 C-D 分离
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const path = graph.shortestPath('A', 'C')
      
      return path.length === 0 // 无路径
    })()
  )

  console.log(
    "4. 自环路径测试:",
    (() => {
      const graph = new Graph()
      
      graph.addVertex('A')
      graph.addEdge('A', 'A') // 自环
      
      const path = graph.shortestPath('A', 'A')
      
      return path.length === 1 &&
             path[0] === 'A'
    })()
  )

  console.log(
    "5. 所有路径测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'D']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const allPaths = graph.findAllPaths('A', 'D')
      
      return allPaths.length >= 2 && // 至少两条路径
             allPaths.every(path => path[0] === 'A' && path[path.length - 1] === 'D')
    })()
  )

  console.log(
    "6. 路径长度测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D', 'E']
      const edges = [['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E'], ['A', 'E']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const pathLength = graph.getPathLength('A', 'E')
      
      return pathLength === 1 // 直接路径长度
    })()
  )

  console.log(
    "7. 路径存在性测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['B', 'C'], ['C', 'D']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const hasPath1 = graph.hasPath('A', 'D')
      const hasPath2 = graph.hasPath('D', 'A') // 反向路径
      
      return hasPath1 === true &&
             hasPath2 === false // 无向图应该有路径，有向图可能没有
    })()
  )

  console.log(
    "8. 复杂路径测试:",
    (() => {
      const graph = new Graph()
      
      // 构建复杂图
      const vertices = ['A', 'B', 'C', 'D', 'E', 'F']
      const edges = [
        ['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'E'], 
        ['D', 'F'], ['E', 'F'], ['A', 'F']
      ]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const path = graph.shortestPath('A', 'F')
      
      return path.length === 2 && // A -> F (最短路径)
             path[0] === 'A' &&
             path[1] === 'F'
    })()
  )

  console.log(
    "9. this上下文路径查找测试:",
    (() => {
      const pathfindingObj = {
        multiplier: 2,
        processPathfinding: function(vertices, edges, start, end) {
          const graph = new Graph()
          vertices.forEach(v => graph.addVertex(v))
          edges.forEach(([from, to]) => graph.addEdge(from, to))
          
          const path = graph.shortestPath(start, end)
          return path.length * this.multiplier
        }
      }
      
      const vertices = ['A', 'B', 'C']
      const edges = [['A', 'B'], ['B', 'C']]
      return pathfindingObj.processPathfinding(vertices, edges, 'A', 'C') === 6 // 3*2=6
    })()
  )

  console.log(
    "10. 复杂对象this绑定路径查找测试:",
    (() => {
      const pathfindingConfigObj = {
        config: { threshold: 2 },
        processWithConfig: function(vertices, edges, start, end) {
          const graph = new Graph()
          vertices.forEach(v => graph.addVertex(v))
          edges.forEach(([from, to]) => graph.addEdge(from, to))
          
          const pathLength = graph.getPathLength(start, end)
          return pathLength >= this.config.threshold
        }
      }
      
      const vertices = ['A', 'B', 'C']
      const edges = [['A', 'B'], ['B', 'C']]
      return pathfindingConfigObj.processWithConfig(vertices, edges, 'A', 'C') === true
    })()
  )

  console.log(
    "11. 路径查找性能测试:",
    (() => {
      const graph = new Graph()
      
      // 构建大图
      const vertices = Array.from({ length: 50 }, (_, i) => `V${i}`)
      vertices.forEach(v => graph.addVertex(v))
      
      // 添加边
      for (let i = 0; i < 50; i += 2) {
        graph.addEdge(`V${i}`, `V${i + 1}`)
      }
      
      const start = performance.now()
      
      const path = graph.shortestPath('V0', 'V49')
      const hasPath = graph.hasPath('V0', 'V49')
      
      const end = performance.now()
      
      return path.length > 0 &&
             hasPath === true &&
             (end - start) < 1000 && // 应该在1秒内完成
             (end - start) > 0
    })()
  )

  console.log(
    "12. 路径查找一致性测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['B', 'C'], ['C', 'D']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      // 多次查找验证一致性
      const path1 = graph.shortestPath('A', 'D')
      const path2 = graph.shortestPath('A', 'D')
      const hasPath1 = graph.hasPath('A', 'D')
      const hasPath2 = graph.hasPath('A', 'D')
      
      return path1.length === path2.length &&
             hasPath1 === hasPath2 &&
             path1.length === 4 &&
             hasPath1 === true
    })()
  )
}

testGraphPathfinding()
